Hai đồ thị G và H được coi là
đẳng cấu, ký hiệu G ~ H, nếu có một quan hệ tương ứng một-một giữa hai tập đỉnh của hai đồ thị sao cho hai đỉnh của đồ thị G kề nhau khi và chỉ khi các đỉnh tương ứng của chúng trong đồ thị H cũng kề nhau.
- Đỉnh: Xem Đồ thị. Đỉnh được vẽ dưới dạng một nút hoặc một điểm. Tập đỉnh của đồ thị G thường được ký hiệu là V(G), hoặc V khi không có nguy cơ hiểu nhầm.
- Đỉnh cha: Xem Cây (có gốc)
- Đỉnh con: Xem Cây (có gốc)
- Đỉnh cắt (cut vertex): là một đỉnh mà nếu loại bỏ nó thì đồ thị tăng số thành phần liên thông.
- Đỉnh gốc: là một đỉnh đặc biệt của cây có gốc. Trong trường hợp này, cây là đồ thị có hướng, đỉnh gốc là đỉnh duy nhất có bậc trong bằng 0.
- Đỉnh lá: Đỉnh có bậc 1, còn được gọi là lá. Thường dùng cho cây có gốc, khi đó lá là đỉnh không có con.
- Đỉnh phát (source): là đỉnh có bậc trong bằng 0.
- Đỉnh thu (sink): là đỉnh có bậc ngoài bằng 0.
- Đỉnh trong (internal vertex): Đỉnh không phải là đỉnh lá.
- Đồ thị: Gồm một tập các đỉnh được nối với nhau bằng các cạnh. Xem chi tiết tại Đồ thị (toán học). Nếu không không được chỉ rõ trong ngữ cảnh, đồ thị được hiểu là đồ thị đơn.
- Đa đồ thị: Đồ thị có đa cạnh nhưng không có khuyên. Có tài liệu quy định là: đồ thị có đa cạnh và có khuyên.
- Đồ thị cha: Một đồ thị cha của G là một đồ thị chứa G với danh nghĩa một đồ thị con. Ta nói rằng đồ thị G chứa đồ thị H nếu có một đồ thị con nào đó của G chính là H hoặc đẳng cấu với H (tùy theo yêu cầu của hoàn cảnh).
- Đồ thị chính quy: là đồ thị có bậc của tất cả các đỉnh bằng nhau.
- Đồ thị có hướng
- Đồ thị có trọng số: Trong đồ thị có trọng số, mỗi cạnh được gắn nhãn là một số, số này được gọi là trọng số của đỉnh. Nói cách khác, đồ thị có trọng số là một đồ thị cùng với một ánh xạ từ tập các cạnh vào tập số thực. Khi không chỉ rõ, một đồ thị luôn được coi là đồ thị không có trọng số.
- Đồ thị con: Một đồ thị con của đồ thị G là một đồ thị mà tập cạnh và tập đỉnh của nó là các tập con của các thành phần tướng ứng của G.
- Đồ thị con bao trùm (spanning subgraph): Đồ thị con H là một đồ thị con bao trùm của đồ thị G nếu tập đỉnh của H trùng với tập đỉnh của G. Ta nói rằng H bao trùm G.
- Đồ thị đầy đủ: Đồ thị đầy đủ bậc n, ký hiệu Kn, là một đồ thị đơn gồm n đỉnh trong đó hai đỉnh bất kỳ đều được nối với nhau bởi một cạnh. Có tất cả n(n-1)/2 cạnh. Đồ thị ví dụ không phải đồ thị đầy đủ.
- Đồ thị đơn: là đồ thị không có đa cạnh và không có khuyên.
- Đồ thị Euler có hướng: là một đồ thị có hướng mà mỗi đỉnh đều có bậc trong bằng bậc ngoài.
- Đồ thị hai phía: là một đồ thị đặc biệt, trong đó tập các đỉnh có thể được chia thành hai tập không giao nhau thỏa mãn điều kiện không có cạnh nối hai đỉnh bất kỳ thuộc cùng một tập.
- Đồ thị hữu hạn: là đồ thị có hữu hạn cạnh và hữu hạn đỉnh. Nếu không được chỉ rõ tính chất, một đồ thị thường được hiểu là hữu hạn.
- Đồ thị hữu hạn địa phương: là đồ thị vô hạn trong đó mỗi cạnh đều có bậc hữu hạn.
- Đồ thị phẳng là đồ thị có thể được vẽ trên mặt phẳng Euclid sao cho không có hai cạnh nào cắt nhau. Đồ thị ví dụ là đồ thị phẳng.
- Đồ thị phi chu trình: là đồ thị không có chu trình. Một đồ thị có hướng là phi chu trình nếu nó không chứa chu trình có hướng.
- Đồ thị phổ dụng (universal graph): Đồ thị phổ dụng của một lớp đồ thị K là một đồ thị đơn nhỏ nhất mà mọi đồ thị là phần tử của K đều là đồ thị con của nó.
- Đồ thị rỗng: là đồ thị không có cạnh và không có đỉnh. Hoặc, nó là một đồ thị không có cạnh nhưng có một số đỉnh n {\displaystyle n} bất kỳ, khi đó, nó được gọi là đồ thị rỗng n {\displaystyle n} đỉnh. (Không có sự thống nhất giữa các tài liệu).
- Đồ thị vòng: là đồ thị chứa một chu trình duy nhất đi qua tất cả các đỉnh, mỗi đỉnh đều có bậc đúng bằng 2.
- Đồ thị vô hạn: là đồ thị có vô hạn cạnh hoặc vô hạn đỉnh hoặc cả hai.
- Đồ thị vô hướng: là đồ thị gồm toàn các cạnh không có hướng.
- Độ dài
Độ dài của một đường đi là số cạnh mà nó đi qua. Đường đi Pn có độ dài n - 1. Trong đồ thị ví dụ, (1, 2, 5, 1, 2, 3) là đường đi có độ dài 5, còn (5, 2, 1) là đường đi đơn có độ dài 2.Độ dài của một chu trìnhlà số cạnh của nó, số này cũng bằng số đỉnh nó đi qua (tính cả bội, nếu một đỉnh được đi qua nhiều lần). Cn có độ dài n. Khác với đường đi, chu trình không được phép có độ dài 0. Các chu trình độ dài 1 là các khuyên. Các chu trình độ dài 2 là các cặp đa cạnh. Trong đồ thị ví dụ, (1, 2, 3, 4, 5, 1) là chu trình độ dài 5.
Hai đường đi được coi là độc lập nếu chúng không có chung đỉnh nào, ngoại trừ đỉnh đầu và đỉnh cuối.Một đỉnh cô lập hoặc đỉnh độc lập là đỉnh không liên thuộc với một cạnh nào, cũng có nghĩa là đỉnh có bậc 0.Một
tập độc lập, hay
tập ổn định, là tập các đỉnh đôi một không kề nhau. Đồ thị con dẫn xuất từ một tập độc lập là một đồ thị rỗng. Trong ví dụ trên, các đỉnh 1, 3 và 6 hợp thành một tập độc lập; các đỉnh 3, 5 và 6 hợp thành một tập độc lập khác.
Số độc lập (indepndence number) của một đồ thị là số cực đại các đỉnh của tập độc lập ứng với đồ thị đó
Một đồ thị G được coi là
đồng cấu với đồ thị H nếu có một ánh xạ từ V(G) tới V(H) sao cho: nếu hai đỉnh kề nhau trong G thì các đỉnh tương ứng của nó cũng kề nhau trong đồ thị H.
- Đường đi (walk/path): là một chuỗi luân phiên giữa đỉnh và cạnh, bắt đầu và kết thúc bởi một đỉnh. Trong đó, mỗi đỉnh là đỉnh đầu cuối của hai cạnh đứng liền trước và liền sau trong chuỗi, các đỉnh đứng liền trước và liền sau một cạnh là các đỉnh đầu cuối của cạnh đó. Khi có hai cạnh giống nhau trên chuỗi có thể loại bỏ bớt các cạnh trùng nhau, sao cho không có cạnh nào của đồ thị cómặt quá một lần trên đường đi. Một đường đi được coi là đónghay một chu trình nếu đỉnh đầu và đỉnh cuối trùng nhau, được coi là mở nếu đỉnh đầu và đỉnh cuối khác nhau. Đường đi qua n đỉnh được ký hiệu là Pn.
- Đường đi có hướng: là một đường đi đơn trong đó mọi cung đều theo cùng một hướng, nghĩa là mọi đỉnh trên đó đều có bậc trong và bậc ngoài bằng 1. Trong đồ thị có hướng, đỉnh v được coi là đến được từ đỉnh u nếu có một đường đi có hướng xuất phát từ u và kết thúc tại v. Có thể gọi đơn giản là đường đi khi ngữ cảnh rõ ràng.
- Đường đi đơn:là đường đi trong đó mỗi đỉnh chỉ được đi qua nhiều nhất một lần.
- Đường đi Euler (Eulerian path): là đường đi qua tất cả các cạnh, mỗi cạnh đúng một lần. Đồ thị ví dụ không có đường đi Euler.
- Đường đi Hamilton (Hamiltonian path): là đường đi đơn qua tất cả các đỉnh trong đồ thị. Đồ thị ví dụ có đường đi Hamilton.
